import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 27
 * Time: 13:44
 */
//牛客 数组中出现次数超过一半的数字
public class Solution9 {
    /*//法一
    public static int MoreThanHalfNum_Solution (int[] numbers) {
        Arrays.sort(numbers);
        int ret = numbers[numbers.length / 2];
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(numbers[i] == ret) {
                count++;
            }
        }
        if(count > numbers.length / 2) {
            return ret;
        }
        return -1;
    }*/

    //法二
    public static int MoreThanHalfNum_Solution (int[] numbers) {
        int time = 0;
        int ret = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(time != 0) {
                if(ret != numbers[i]) {
                    time--;
                }else {
                    time++;
                }
            }else {
                ret = numbers[i];
                time = 1;
            }
        }
        time = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(numbers[i] == ret) {
                time++;
            }
        }
        if(time > numbers.length / 2) {
            return ret;
        }
        return -1;
    }
}
